package nodelist

// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnv1oc/
// 判断链表是否回文
// 算法: 双指针 + 翻转链表
func IsPalindrome(head *ListNode) bool {
	if nil == head {
		return true
	}
	// 先通过双指针找到中间位置
	midNode := head
	fastNode := head
	for {
		midNode = midNode.Next
		fastNode = fastNode.Next
		if nil == fastNode {
			break
		}
		fastNode = fastNode.Next
		if nil == fastNode {
			break
		}
	}
	// 特殊情况: 链表大小为1，那么 midNode 从一开始也是空，直接返回true
	if nil == midNode {
		return true
	}
	// 翻转后半部分链表
	right := reverse(midNode)
	left := head
	for nil != right {
		if left.Val != right.Val {
			return false
		}
		left = left.Next
		right = right.Next
	}
	return true
}

// 反转链表
// 不会影响原链表
func reverse(node *ListNode) *ListNode {
	newTail := new(ListNode)
	newTail.Val = node.Val
	currentNode := newTail
	tempNext := node.Next
	for nil != tempNext {
		newNext := new(ListNode)
		newNext.Val = tempNext.Val
		newNext.Next = currentNode
		currentNode = newNext
		tempNext = tempNext.Next
	}
	return currentNode
}
